class GridMaster(object):
    def canMove(self, direction):
        """
        :type direction: str
        :rtype bool
        """

    def move(self, direction):
        """
        :type direction: str
 .       :rtype int
        """

    def isTarget(self):
        """
        :rtype bool
        """


import collections
import copy

import heapq
class Solution(object):
    def findShortestPath(self, master):
        self.d = {}
        self.flag = None

        def dfs(x, y, robot):
            if not robot.isTarget():
                if (x, y) not in self.d:
                    self.d[(x, y)] = collections.defaultdict(dict)
                    if robot.canMove('U'):
                        new_robot = copy.copy(robot)
                        self.d[(x, y)][(x - 1, y)] = new_robot.move('U')
                        dfs(x - 1, y, new_robot)
                    if robot.canMove('D'):
                        new_robot = copy.copy(robot)
                        self.d[(x, y)][(x + 1, y)] = new_robot.move('D')
                        dfs(x + 1, y, new_robot)
                    if robot.canMove('L'):
                        new_robot = copy.copy(robot)
                        self.d[(x, y)][(x, y - 1)] = new_robot.move('L')
                        dfs(x, y - 1, new_robot)
                    if robot.canMove('R'):
                        new_robot = copy.copy(robot)
                        self.d[(x, y)][(x, y + 1)] = new_robot.move('R')
                        dfs(x, y + 1, new_robot)
            else:
                self.flag = (x, y)

        dfs(0, 0, master)
        if not self.flag:
            return -1

        now = {(0, 0)}
        node = (0, 0)
        st = []
        for x, y in self.d[node]:
            st.append([self.d[node][(x, y)], x, y])
        heapq.heapify(st)
        while st:
            while st and (st[0][1], st[0][2]) in now:
                heapq.heappop(st)
            if st:
                next_dist, next_x, next_y = heapq.heappop(st)
                if (next_x, next_y) == self.flag:
                    return next_dist
                now.add((next_x, next_y))
                for x, y in self.d[(next_x, next_y)]:
                    heapq.heappush(st, [self.d[(next_x, next_y)][(x, y)] + next_dist, x, y])


